"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

from typing import Optional

from python.mypackage import Node


class Solution:
    """
    方法：复制带随机指针的链表
        1. 在每个节点后复制一个新节点
        2. 设置新节点的random指针
        3. 分离原链表和复制的链表
    
    Args:
        head: 链表头节点
    
    Returns:
        复制后的新链表头节点
    
    Time: O(n) - 需要遍历链表3次
    
    Space: O(1) - 只使用常数额外空间
    """
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if head is None:
            return None
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        
        new_head = head.next
        cur = head
        while cur.next.next:
            copy = cur.next
            cur.next = copy.next
            copy.next = copy.next.next
        cur.next = None
        return new_head